package com.datastructures.tree;

/**
 * 二叉排序树
 *
 * @author MaoLin Wang
 * @date 2019/11/1113:28
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }
        binarySortTree.infixOrder();
        binarySortTree.delNode(2);
        binarySortTree.delNode(5);
        binarySortTree.delNode(9);
        binarySortTree.delNode(12);
        binarySortTree.delNode(7);
        binarySortTree.delNode(3);
        binarySortTree.delNode(10);
        binarySortTree.delNode(1);
        binarySortTree.getRoot();
        System.out.println("111111111");
        binarySortTree.infixOrder();
    }
}

//创建二叉排序树
class BinarySortTree {
    private Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }

    }
    public void getRoot(){
        System.out.println(root);
    }

    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        }
    }

    //查找要删除的节点
    public Node find(int data) {
        if (root == null) {
            return null;
        } else {
            return root.find(data);
        }
    }

    //查找要删除的父节点
    public Node findparentNode(int data) {
        if (root == null) {
            return null;
        } else {
            return root.findParentNode(data);
        }
    }

    /**
     * 删除节点：
     * 一、删除的是叶子节点
     * 1.先找到要删除的节点
     * 2.找到该节点的父节点parentNode
     * 3.确定该节点时parentNode的左孩子还是右孩子
     * 4.根据前面的情况来删除
     * 二、删除只有一颗子树的节点
     * 1.先找到要删除的节点targetNode
     * 2.找到该节点的父节点parentNode
     * 3.确定该节点的子节点是左子节点还是右子节点
     * 4.确定该节点是parentNode的左节点还是右节点
     * 5.targetNode有左子节点
     * 若targetNode是parentNode的左子节点
     * parentNode.lchild=targetNode.lchild
     * 若targetNode是parentNode的右子节点
     * parentNode.rchild=targetNode.lchild
     * 5.targetNode有右子节点
     * 若targetNode是parentNode的左子节点
     * parentNode.lchild=targetNode.rchild
     * 若targetNode是parentNode的右子节点
     * parentNode.rchild=targetNode.rchild
     * 三、删除有两颗子树的节点
     * 1.先找到要删除的节点targetNode
     * 2.找到该节点的父节点parentNode
     * 3.从targetNode找到最小的节点，用一个临时变量temp存储
     * 4.删除该最小节点
     * 5.targetNode.data=temp
     */

    //删除节点
    public void delNode(int data) {
        if (root == null) {
            return;
        } else {
            Node targetNode = find(data);
            if (targetNode == null) {
                return;
            }
            //该树只有一个根节点
            if (root.lchild == null && root.rchild == null) {
                root = null;
                return;
            }
            Node parentNode = findparentNode(data);
            //待删除的节点是叶子节点
            if (targetNode.lchild == null && targetNode.rchild == null) {
                if (parentNode.lchild != null && parentNode.lchild.data == data) {
                    //待删除节点是父节点的左子节点
                    parentNode.lchild = null;
                } else if (parentNode.rchild != null && parentNode.rchild.data == data) {
                    //待删除节点是父节点的左子节点
                    parentNode.rchild = null;
                }
            } else if (targetNode.lchild != null && targetNode.rchild != null) {//有两颗子树
                /*
                  1.先找到要删除的节点targetNode
                 2.找到该节点的父节点parentNode
                 3.从targetNode找到最小的节点，用一个临时变量temp存储
                 4.删除该最小节点
                 5.targetNode.data=temp
                 */
                Node temp=targetNode.rchild;
                while (temp.lchild!=null){
                    temp=temp.lchild;
                }
                delNode(temp.data);
                targetNode.data=temp.data;

            } else {//待删除节点只有一颗子树
                //待删除节点有左子节点
                if (targetNode.lchild != null) {
                    if (parentNode==null){
                        root=targetNode.lchild;
                    }else {
                        //如果待删除节点是父节点的左子节点
                        if (parentNode.lchild.data == data) {
                            parentNode.lchild = targetNode.lchild;
                        } else {
                            //待删除节点是父节点的右子节点
                            parentNode.rchild = targetNode.lchild;
                        }
                    }

                } else {//待删除节点有右子节点

                    if (parentNode==null){
                        root=targetNode.rchild;
                    }else {
                        if (parentNode.lchild.data == data) {
                            //待删除节点是父节点的左子节点
                            parentNode.lchild = targetNode.rchild;
                        } else {
                            //待删除节点是父节点的右子节点
                            parentNode.rchild = targetNode.rchild;
                        }
                    }

                }
            }
        }
    }

}

class Node {
    int data;
    Node lchild;
    Node rchild;

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }

    public Node() {
    }

    public Node(int data) {
        this.data = data;
    }

    //添加节点
    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (node.data < this.data) {
            //当前左孩子为空
            if (this.lchild == null) {
                //让左孩子为node
                this.lchild = node;
            } else {
                this.lchild.add(node);
            }

        } else {
            if (this.rchild == null) {
                this.rchild = node;
            } else {
                this.rchild.add(node);
            }
        }
    }


    /**
     * 查找待删除节点
     *
     * @param data 待删除节点值
     * @return
     */
    public Node find(int data) {
        if (data == this.data) {
            return this;
        } else if (data < this.data) {
            if (this.lchild == null) {
                return null;
            }
            return this.lchild.find(data);
        } else {
            if (this.rchild == null) {
                return null;
            }
            return this.rchild.find(data);
        }
    }

    /**
     * 查找待删除节点的父节点
     *
     * @param data 待查询的节点的值
     * @return
     */
    public Node findParentNode(int data) {
        //当前节点是待删除节点的父节点
        if ((this.lchild != null && this.lchild.data == data) || (this.rchild != null && this.rchild.data == data)) {
            return this;
        } else {
            //查找的值比当前节点小，且当前节点有左子节点
            if (data < this.data && this.lchild != null) {
                //向左子树递归查询
                return this.lchild.findParentNode(data);
            } else if (data >= this.data && this.rchild != null) {
                //向右子树递归查询
                return this.rchild.findParentNode(data);
            } else {
                return null;
            }
        }
    }

    public void infixOrder() {
        if (this.lchild != null) {
            this.lchild.infixOrder();
        }
        System.out.println(this);
        if (this.rchild != null) {
            this.rchild.infixOrder();
        }
    }
}